package com.company.笔试.常用排序算法.归并;

import com.company.笔试.常用排序算法.array.ArrayData;

import java.util.Arrays;

/**
 * @ClassName Solution
 * @Description TODO
 * @Author ylr
 * @Date 2021/7/20 18:52
 * @Version 1.0
 */
public class Solution {
    public static void main(String[] args) {
        int[] a = new ArrayData().getA();
        MargeSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));

    }

    public static void MargeSort(int[] arr, int left, int right) {
        if (arr == null || left >= right) return;
        int mid = (left + right) / 2;
        MargeSort(arr, left, mid);
        MargeSort(arr, mid + 1, right);
        marge(arr, left, right);
    }

    private static void marge(int[] arr, int left, int right) {
        int[] temp = new int[right - left + 1];//tmp是汇总2个有序区的临时区域
        int mid = (left + right) / 2;          //mid 是左右边界
        // 将左右两个区域合并到temp中
        int k=0;
        int i=left;
        int j=mid+1;
        while (i<=mid&&j<=right){
            temp[k++] = arr[i]>=arr[j]?arr[j++]:arr[i++];//从小到大
        }
        //判断有没有剩下的
        while (i<=mid){
            temp[k++] = arr[i++];
        }
        while (j<=right){
            temp[k++] = arr[j++];
        }

        //temp就是left-right有序的区域了，接下来整合到arr中
        for (int l = 0; l <k ; l++) {
            arr[left+l] = temp[l];
        }
    }


}
